googologytestingfandomcom-20200215-history
Introduction to ordinal collapsing functions
Please see talk page before editing. Feel free to add and remove which ordinals and subsections are added. Also, please add definitions for the OCFs. We want them to be as simple as possible, and also easy to explain. Description of OCFs and why they're needed Ordinal notations start with Cantor's normal form, where ordinals below \(\varepsilon_0\) are represented as a finite decreasing sum of multiples of powers of omega, whose exponents are also ordinals represented in cantor's normal form. Then, new notations can be invented, like epsilon notation enumerating the fixed points of \(\alpha\rightarrow\omega^{\alpha}\), zeta notation enumerating its fixed points, eta notation enumerating the fixed points of that! Then, they can be generalized into the Veblen phi function \(\varphi(\alpha,\beta)\). The gamma function enumerates the fixed points of \(\alpha\rightarrow\varphi(\alpha,0)\). The gamma function is a subset of the Multi-argument veblen phi function which has multiple arguments, which can then be extended to transfinite arguments. Now you could extend it even further, rather naively. Or you could create an ordinal collapsing function. An ordinal collapsing function takes uncountable ordinals as input and outputs countable ordinals. Madore's psi Madore's psi is defined like this: \begin{eqnarray*} C_0(\alpha) &=& \{0, 1, \omega, \Omega\}\\ C_{n+1}(\alpha) &=& \{\gamma + \delta, \gamma\delta, \gamma^{\delta}, \psi(\eta) | \gamma, \delta, \eta \in C_n (\alpha); \eta < \alpha\} \\ C(\alpha) &=& \bigcup_{n < \omega} C_n (\alpha) \\ \psi(\alpha) &=& \min\{\beta \in \Omega|\beta \notin C(\alpha)\} \\ \end{eqnarray*} This looks quite cryptic, so here is a less technical definition: Let \(C(\alpha)\) be the set of all ordinals that can be expressed in terms of \(0, 1, \omega, \Omega\) and the operations addition, multiplication, exponentiation, and \(\kappa\rightarrow\psi(\kappa)\), the latter only if \(\kappa\) is less than \(\alpha\). \(\psi(\alpha)\) is the first ordinal not in \(C(\alpha)\). For inputs below \(\Omega\) the function is equivalent to \(\varepsilon_x\) and \(\psi(\Omega)\) is equal to \(\zeta_0\). This function is limited at the bachmann-howard ordinal. Up next we will explain another commonly-used ordinal collapsing function. Bachmann-Howard ordinal Let \(\Omega=\omega_1\) be the smallest uncountable ordinal. \(\begin{eqnarray*} C_0(\alpha,\beta) &=& \beta\cup\{\Omega\} \\ C_{n+1}(\alpha,\beta) &=& \{\gamma+\delta:\gamma,\delta\in C_n(\alpha,\beta)\} \\ &\cup& \{\omega^\gamma:\gamma\in C_n(\alpha,\beta)\wedge\gamma\geq\Omega\} \\ &\cup& \{\vartheta(\gamma):\gamma\in C_n(\alpha,\beta)\wedge\gamma<\alpha\} \\ C(\alpha,\beta) &=& \bigcup_{n<\omega}C_n(\alpha,\beta) \end{eqnarray*}\) \(C(\alpha,\beta)\) can also be seen as the closure of \(\{\Omega\}\) and all of the ordinals less than \(\beta\) under addition, base-\(\omega\) exponentiation (to uncountable ordinals), and the \(\vartheta\) function to ordinals less than \(\alpha\). \(\vartheta(\alpha) = \min\{\beta>0:\Omega\cap C(\alpha,\beta)\subseteq\beta\}\) \(\vartheta(\alpha)\) can also be seen as the smallest ordinal \(\beta\) such that all countable ordinals in \(C(\alpha,\beta)\) are less than \(\beta\); \(\beta\) is the smallest ordinal such that you can't create a larger countable ordinal from the ordinals less than \(\beta\), \(\Omega\), and the operations \(+\), \(\gamma\mapsto\omega^\gamma\) (for \(\gamma\geq\Omega\)), and \(\gamma\mapsto\vartheta(\gamma)\) (for \(\gamma<\alpha\)). Now, let's say that we are trying to find \(\vartheta(\alpha)\), where \(\alpha\) is some countable ordinal. <--will continue to explain later--> Fundamental sequences Takeuti-Feferman-Buchholz ordinal extensions of the theta and psi functions Fundamental sequences SGH vs. FGH \(\vartheta(\Phi(1,0))\) Same as \(\psi(\psi_I(0))\), but doesn't need explanation of \(I\). \(\Phi\) is the Veblen function on \(\alpha\mapsto\omega_\alpha\) Fundamental sequences \(\psi(\Lambda_0)\) Note: For this section, to make understanding the cardinals easier, we drop 'weakly' from the definitions of \(\alpha\)-inaccessibility, and simply have the \(\alpha\)-inaccessible cardinals mean the weakly \(\alpha\)-inaccessibles, not the strongly \(\alpha\)-inaccessibles. This removes potential confusion. Call a cardinal \(0\)-inaccessible iff it is uncountable and regular. Now, call a cardinal \(\alpha+1\)-inaccessible iff it is \(\alpha\)-inaccessible and a limit of \(\alpha\)-inaccessible cardinals, and, for limit ordinals \(\lambda\), call a cardinal \(\lambda\)-inaccessible if it is \(\alpha\)-inaccessible for all \(\alpha<\lambda\). Lastly, we can call a cardinal \(\kappa\) which is \(\kappa\)-inaccessible hyper-inaccessible and let \(\Lambda_0\) be the smallest hyper-inaccessible cardinal. Although not relevant to the definition directly, please not that it's impossible to prove that even a \(1\)-inaccessible cardinal exists in ZFC. Therefore, for this section, we instead work in the system ZFC + 'there exists a hyper-inaccessible cardinal'. Now, we can define a series of functions, \(\text I_\alpha\), which enumerate the \(\alpha\)-inaccessible cardinals less than \(\Lambda_0\), and their limit points. Formally, we write: \(\text I_\alpha = \text{enum}(\text{cl}(\{\beta<\Lambda_0:\beta\text{ is }\alpha\text{-inaccessible}\}))\) Where \(\text{enum}(S)\) is the unique increasing function that enumerates the elements of \(S\) (so \(\text{enum}(\{\omega^3,\omega^4,\omega^5,\cdots,\omega^{\omega^2},\omega^{\omega^2+1}\})\) is the function \(\alpha\mapsto\omega^{3+\alpha}\) defined on \(\omega^2+2\mapsto S\))), and \(\text{cl}(S)\) is \(S\cup\{\beta:\sup(S\cap\beta)=\beta\}\): the union of \(S\) and it's limit points. Also, similarly to last time, restrict \(\pi\) to uncountable regular cardinals (equivalently: \(0\)-inaccessible). With this, we can define our \(\psi\) function: \(\begin{eqnarray*} C_0(\alpha,\beta) &=& \beta \\ C_{n+1}(\alpha,\beta) &=& \{\gamma+\delta:\gamma,\delta\in C_n(\alpha,\beta)\} \\ &\cup& \{\text I_\gamma(\delta):\gamma,\delta\in C_n(\alpha,\beta)\} \\ &\cup& \{\psi_\pi(\gamma):\gamma,\pi\in C_n(\alpha,\beta)\wedge\gamma<\alpha\} \\ C(\alpha,\beta) &=& \bigcup_{n<\omega}C_n(\alpha,\beta) \\ \psi_\pi(\alpha) &=& \min\{\beta:C(\alpha,\beta)\cap\pi\subseteq\beta\} \end{eqnarray*}\) Rathjen's ordinal This ordinal is equal to \(\psi(\chi(\varepsilon_{M+1}))\). Category:Introduction articles Category:Transfinite ordinals